1. Field of the Invention
The present invention relates to a forward inference system processed by a computer and, more particularly, to an improved element checking system for checking different elements which are used in the forward inference system, and a method therefor.
2. Description of the Prior Art
The forward inference system is developed, for example, for a production system which makes a decision based on a number of known facts which are stored as elements of a working memory in a computer. The decision which is made by the forward inference system is to produce a new fact in a form of new element which is added to the working memory, to delete or revise a particular fact, i.e., element, from the working memory, to start a new program or to produce an alarm, or any other system control which the computer may perform.
The production system is constructed by three different statements, each of which will be explained below.
The first one is a pattern formatting statement for providing various patterns to be stored in a pattern memory. It is assumed that the following patterns are made.
literalize Ape (Place Weight) PA1 literalize thing (Name Place) PA1 literalize Status (Movement Thing) PA1 literalize Thing (Height Width Weight) PA1 Ape (Place: Room 1) PA1 Thing (Name: Banana, Place: Room 1) PA1 Ape (Place: $ Room) PA1 Thing (Name: Banana, Place: $ Room) PA1 Status (Movement: eat, Thing: banana).
In each of the above statements, "literalize" indicates to prepare the pattern that follows. According to the example given above, the first pattern statement is for "Ape". Here, "Ape" represents the pattern name and each of "Place" and "Weight" represents attributes. According to the second example, "Thing" is the pattern name and "Name" and "Place" are the attributes. According to the third example, "Status" is the pattern name and "Movement" and "Thing" are the attributes. According to the fourth example, "Thing" is the pattern name and "Height", "Width" and "Weight" are the attributes.
The second statement is the element of a fact. Each element is constructed by a pattern name and one or more pairs of attribute and value. The pattern name is defined by the above-mentioned pattern making procedure. Two examples of the element are shown below.
The first example has the element name Ape and one attribute-value pair. The attribute is Place and its value is Room 1. This element tells, for example, a fact that "an ape is in the Room 1", according to the previously determined interpreting rule.
The second example has the element name Thing and two attribute-value pairs. In the first attribute-value pair, the attribute is Name and its value is Banana. In the second attribute-pair, the attribute is Place and its value is Room 1. This element tells, for example, a fact that "a thing in the Room 1 is banana", according to the previously determined interpreting rule. The fact will be stored in the working memory as the production system reads the program.
The third statement consists of IF-THEN rules called production rules. An example of the production rule, which is called "Ape Eats Banana", shown below.
If facts given by the following elements.
are satisfied, then, make a new fact given by the following element
The above IF-THEN rule is symbolically shown below. ##STR1## In the IF-THEN rules, the elements appearing after the "IF" statement are called "condition elements". In the above example, condition elements are "Ape (Place: $ Room)" and "Thing (Name: Banana, Place: $ Room)". Here, the symbol $ indicates that the value is variable. Thus, the value of the Place attribute of the first element is equal to the value of the Place attribute of the second element. The newly produced element by the above given IF-THEN statement tells, for example, a fact that "banana is eaten". Thus the "Ape Eats Banana" production rule can be interpreted such that, when the conditions "an ape is in a room" and "a banana is in the same room" are satisfied, it is inferred that "banana is eaten". The inferred fact is then added to the working memory to further infer some other new fact or some new step.
According to the forward inference system, the condition element of the rule and the element in the working memory are compared. Thus, it takes time to find a proper combination between the existing rule and the element in the working memory.
For example, if the rules are compared with existing elements in the order of elements stored in memory, it is necessary to carry out the comparison repeatedly; The number of such a comparison will be increased by (number of rules).times.(elements in the working memory), each time the element in the working memory is added or deleted. Thus, an enormous amount of time is needed for the element checking.
To solve this, an improved method has been proposed, according to which, only the rules with elements which correspond to the newly added, deleted or converted element in the working memory are checked, provided that the rule has been previously converted to the network.
In order to prosecute the production rule, elements are checked by a network having nodes linked together. The prior art network for the production rule, Ape Eats Banana, is shown in FIG. 1. The elements taken out from the working memory and passed into the network are called tokens. The network shown in FIG. 1 consists of: distribution node N1 which has one input Pa for receiving tokens one at a time and a plurality of outputs, such as two outputs in the case shown in FIG. 1; element name check nodes N2 and N3 for checking the element name; attribute check node N4; value check node N5; and terminal node N6. During the check process in the network, many features of the element are checked. The features can be divided into two classes. The first class, which is called intra-element feature, is the one that involves only one element. In the above example of FIG. 1, nodes N2, N3 and N4 are provided to check the intra-element features. The second class, which is called inter-element features, is the one that involve two or more elements. In FIG. 1, node N5 is provided to check the inter-element feature. Therefore, node N5 is coupled with memories M1 and M2 for storing codes representing the elements which have arrived at Node N5 from nodes N2 and N4, respectively.
In operation, the distribution node N1 receives a token through input Pa from the working memory and distributes it to element name check node N2 at which point it is checked whether the element name is Ape or not. If not, the token is rejected and sent back to distribution node N1 which then sends the token to next element name check node N3. The element check is carried out until the correct name of the applied token is found. When the correct element name of the applied token is not found, the token is expelled from the network, and the next token enters the network.
If the entered token has the element name, Ape, the token is transferred from node N1 to node N2 and further to node N5 at which point a code representing the element Ape is stored in memory M1 and then, the token is expelled from the network since there is no element Thing stored therein to carry out the check of node N5.
If the next entered token has the element name, Thing, the token is transferred through nodes N1, N2, N1, N3, N4 and N5. At node N5, a code representing the element Thing is stored in memory M2 and then, it is checked whether or not the value of the Place attribute of the element Ape, which is called by the code stored in memory M1, is equal to the value of the Place attribute of the element Thing. When these Place attributes have the same value, such as $ Room, these elements are joined so as to enable the execution of the production rule "Ape Eats Banana".
Usually, the forward inference system has a plurality of rules. Thus, for the newly added element in the working memory, there will be a plurality of rules for the execution of the production. Of all the possible rules, one rule is selected and the network is processed for producing a new element. If "Ape eat Banana" is selected and executed, a newly produced element will be produced by the production rule; It is then added to the working memory and is checked through the networks for checking various rules.
Thus, according to the prior art forward inference system, the element check is carried out such that, in the first level (node N1) of the network, the token is distributed sequentially to different element name check nodes; Further, in the second level (nodes N2 and N3) of the network, the name of the distributed token is checked one at a time. In the third level (nodes N4 and N5) of the network, the attribute and its value, if any, are checked. In the fourth level (node N6) of the network, a decision is made so as to execute the production rule.
According to the prior art element checking system, there is such a disadvantage that it takes a long time before the network produces a decision. Particularly, the execution carried out in the first level takes a long time, because even the tokens which do not have the corresponding element name in the second level are also executed.